import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树-层序遍历-力扣102
 */
public class Practice_30 {
    public static void main(String[] args) {

        TreeNode head=new TreeNode(1);

        head.left=new TreeNode(2);

        head.right=new TreeNode(3);

        head.left.left=new TreeNode(4);

        head.left.right=new TreeNode(5);

        head.right.left=new TreeNode(6);

        head.right.right=new TreeNode(7);


        List<List<Integer>> list= levelOrder(head);


    }

    /**
     * 层序遍历（广度优先）
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);//先放第一个节点
        }
        while(!queue.isEmpty()){

            int size=queue.size();//注意要在这里取长度
            List<Integer> list=new ArrayList<>();

            while(size>0){
                TreeNode node=queue.peek();//让节点每次往后移动

                list.add(queue.poll().val) ;//队列里弹出值
                if(node.left!=null){//加入左边的值
                    queue.offer(node.left);

                }

                if(node.right!=null){//加入右边的值
                    queue.offer(node.right);
                }
                size=size-1;//数量减少1
            }
            result.add(list);
        }
        return result;
    }


    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
    }
}
